from mode import List

"""
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。
这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。
一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 
如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
     3
    / \
   2   3
    \   \ 
     3   1
输出: 7 
解释:小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.
示例 2:
输入: [3,4,5,1,3,null,1]
     3
    / \
   4   5
  / \   \ 
 1   3   1
输出: 9
解释:小偷一晚能够盗取的最高金额= 4 + 5 = 9.
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rob(self, root: TreeNode) -> int:
        # dp解法，建立两个表（哈希表映射）
        # 函数f(node)为打劫当前节点node时的最大收益
        # 函数g(node)为不打劫当前节点node时的最大收益
        # 两种情况：
        # 1 当前节点被打劫，则其左子节点和右子节点没有被打劫:
        #   f(node)=g(node.left)+g(node.right)+node.val
        # 2 当前节点没有被打劫，则其左子节点和右子节点可以被打劫或不打劫:
        #   g(node)=max(f(node.left),g(node.left))+max(f(node.right),g(node.right))
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            dfs(root.right)
            f[root] = g[root.left] + g[root.right] + root.val
            g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right])

        f = {None: 0}
        g = {None: 0}
        dfs(root)
        return max(f[root], g[root])


if __name__ == "__main__":
    node1 = TreeNode(3)
    node2 = TreeNode(4)
    node3 = TreeNode(5)
    node4 = TreeNode(1)
    node5 = TreeNode(3)
    node6 = TreeNode(1)
    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5
    node3.right = node6
    A = Solution()
    print(A.rob(node1))
